package com.zs.letcode.top_interview_questions;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 旋转数组
 * 给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。
 * <p>
 * <p>
 * <p>
 * 进阶：
 * <p>
 * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
 * 你可以使用空间复杂度为O(1) 的原地算法解决这个问题吗？
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,2,3,4,5,6,7], k = 3
 * 输出: [5,6,7,1,2,3,4]
 * 解释:
 * 向右旋转 1 步: [7,1,2,3,4,5,6]
 * 向右旋转 2 步: [6,7,1,2,3,4,5]
 * 向右旋转 3 步: [5,6,7,1,2,3,4]
 * 示例2:
 * <p>
 * 输入：nums = [-1,-100,3,99], k = 2
 * 输出：[3,99,-1,-100]
 * 解释:
 * 向右旋转 1 步: [99,-1,-100,3]
 * 向右旋转 2 步: [3,99,-1,-100]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 2 * 104
 * -231 <= nums[i] <= 231 - 1
 * 0 <= k <= 105
 * 相关标签
 * 数组
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xm42hs/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/5/28 09:19
 */
public class Chapter17 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.rotate(new int[]{1, 2, 3, 4, 5, 6, 7}, 3);
    }

    private static class Solution {
        public void rotate(int[] nums, int k) {
            k = k % nums.length;
            int[] result = new int[nums.length];
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < nums.length - k; i++) {
                queue.add(nums[i]);
            }
            int index = 0;
            for (int i = nums.length - k; i < nums.length; i++) {
                result[index] = nums[i];
                index++;
            }
            while (!queue.isEmpty()) {
                result[index] = queue.poll();
                index++;
            }
            for (int i = 0; i < nums.length; i++) {
                nums[i] = result[i];
            }
        }

        /**
         * 方法一：使用额外的数组
         *
         * @param nums
         * @param k
         */
        public void rotate1(int[] nums, int k) {
            int n = nums.length;
            int[] newArray = new int[n];
            for (int i = 0; i < n; i++) {
                newArray[(i + k) % n] = nums[i];
            }
            System.arraycopy(newArray, 0, nums, 0, n);
        }

        /**
         * 方法二：环状替换
         */
        public void rotate2(int[] nums, int k) {
            int n = nums.length;
            k = k % n;
            int count = gcd(k, n);
            for (int start = 0; start < count; start++) {
                int current = start;
                int prev = nums[start];
                do {
                    int next = (current + k) % n;
                    int temp = nums[next];
                    nums[next] = prev;
                    prev = temp;
                    current = next;
                } while (start != current);
            }
        }

        private int gcd(int k, int n) {
            return n > 0 ? gcd(n, k % n) : k;
        }

        /**
         * 方法三：数组翻转
         */
        public void rotate3(int[] nums, int k) {
            k %= nums.length;
            reverse(nums, 0, nums.length - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length - 1);
        }

        private void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start += 1;
                end -= 1;
            }
        }
    }
}
